package ThirdWeek;

public class Sunday {
    //LCR 173、点名
    public  int takeAttendance(int[] records) {
        //二分查找
        //我们的根据暴力枚举的方法知道，任意一个位置i 当下标和对应位置的值相等的时候，那么说明其之前位置都是对应的，要不就会篡位
        //也就是：arr[i] == i left = i + 1;
        //      arr[i] != i right = i; 因为我也不知道这个i位置是否是缺席的人，如果跳过就不对了
        int left = 0,right = records.length - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if (records[mid] == mid) {
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        //处理一下，当就只有一个0时候，返回的是1
        return left == records[left] ? left + 1 : left;
    }

    public static int takeAttendance1(int[] records) {
        //暴力枚举
        if (records[0] == 1) {
            return 0;
        }
        for (int i = 0; i < records.length; i++) {
            if (records[i] != i) {
                return i;
            }
        }
        return records.length;
    }

    public static void main(String[] args) {
        int[] arr = {0,1,2,3,5};
        System.out.println(takeAttendance1(arr));
    }
    //153、寻找旋转排序数组中的最小值
    public int findMin(int[] nums) {
        //二分查找:
        //我们可以根据不管旋转多少次，都是存在两段的，都是上升，
        // 一个是往非常大的值上升，另一段时从最小值开始上升有可能会上升到第一段的开始位置，也可能是比起小
        //我们把旋转后的值的right位置，设为x，就此开始比较
        int left = 0,right = nums.length - 1;
        int t = nums[right];
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > t) {
                //在第一段位置，这里没有我们要找的数据，我们的left要争取跳出这个区间
                left = mid + 1;
            }else {
                right = mid;
            }
        }

        return nums[left];
    }

    //162、寻找峰值
    public int findPeakElement(int[] nums) {
        //这里我们可以找到二段性，任意的一个值，和其 +1 位置的数据进行比较，
        // 当nums[i] < nums[i+1]的时候，右面一定存在峰值，i这个位置就不是峰值 left = i + 1
        // 当nums[i] > nums[i+1]的时候，左面一定存在峰值，i这个位置可能是峰值 right = i
//        int left = 0,right = nums.length - 1;
//        while(left < right) {
//            int mid = left + (right - left) / 2;
//            if (nums[mid] < nums[mid + 1]) {
//                left = mid + 1;
//            }else {
//                right = mid;
//            }
//        }
//
//        return left;

        //如果使用：当nums[i] > nums[i-1]的时候，右面一定存在峰值，i这个位置可能是峰值 left = i
        //        当nums[i] < nums[i-1]的时候，左面一定存在峰值，i这个位置就不是峰值 right = i - 1
        int left = 0,right = nums.length - 1;
        while(left < right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] > nums[mid - 1]) {
                left = mid;
            }else {
                right = mid - 1;
            }
        }

        return left;
    }

    //852、山峰数组的山顶索引
    public int peakIndexInMountainArray(int[] arr) {
        //因为可以使其数组分为两段，为：上升趋势的左面，下降趋势的右面，我们的峰顶在左面
        int left = 0,right = arr.length - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (arr[mid] > arr[mid - 1]) {
                //上升趋势，并且峰值在这段中
                left = mid;
            }else {
                right = mid - 1;
            }
        }

        return left;
    }

    public int peakIndexInMountainArray1(int[] arr) {
        //暴力枚举，时间复杂度：O(N)
        for(int i = 1;i < arr.length - 1;i++) {
            if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
                return i;
            }
        }
        return -1;
    }
}
